package com.leetcode.algorithm.y19.m04;

/**
 * leetcode-cn.com
 * (done)997. 找到小镇的法官
 * (done)62. 不同路径
 * (done)63. 不同路径 II
 * @author: jie.deng
 * @time: 2019年4月4日 上午10:27:58
 */
public class MySolution0403 {
    
    /**
     * 997. 找到小镇的法官
     * 
     * 在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。
     * 
     * 如果小镇的法官真的存在，那么：
     * 
     * 小镇的法官不相信任何人。
     * 每个人（除了小镇法官外）都信任小镇的法官。
     * 只有一个人同时满足属性 1 和属性 2 。
     * 给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。
     * 
     * 如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：N = 2, trust = [[1,2]]
     * 输出：2
     * 示例 2：
     * 
     * 输入：N = 3, trust = [[1,3],[2,3]]
     * 输出：3
     * 示例 3：
     * 
     * 输入：N = 3, trust = [[1,3],[2,3],[3,1]]
     * 输出：-1
     * 示例 4：
     * 
     * 输入：N = 3, trust = [[1,2],[2,3]]
     * 输出：-1
     * 示例 5：
     * 
     * 输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
     * 输出：3
     *  
     * 
     * 提示：
     * 
     * 1 <= N <= 1000
     * trust.length <= 10000
     * trust[i] 是完全不同的
     * trust[i][0] != trust[i][1]
     * 1 <= trust[i][0], trust[i][1] <= N
     * @param N
     * @param trust
     * @return
     */
    public int findJudge(int N, int[][] trust) {
        boolean[] excludeArr = new boolean[N + 1];
        int[] trustedCnt = new int[N + 1];
        for (int i = 0; i < trust.length; i++) {
            excludeArr[trust[i][0]] = true; // trust[i][0]不可能是法官，加入排除数组
            if (!excludeArr[trust[i][1]]) {
                trustedCnt[trust[i][1]]++; // 更新可能的法官被信任的次数
            }
        }
        int judge = 0;
        for (int i = 1; i <= N; i++) {
            if (!excludeArr[i]) {
                if (judge == 0) {
                    judge = i;
                } else {
                    return -1;
                }
            }
        }
        return trustedCnt[judge] == (N - 1) ? judge : -1;
    }
    
    /**
     * 62. 不同路径
     * 
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     * 
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     * 
     * 问总共有多少条不同的路径？
     * 
     * 
     * 
     * 例如，上图是一个7 x 3 的网格。有多少可能的路径？
     * 
     * 说明：m 和 n 的值均不超过 100。
     * 
     * 示例 1:
     * 
     * 输入: m = 3, n = 2
     * 输出: 3
     * 解释:
     * 从左上角开始，总共有 3 条路径可以到达右下角。
     * 1. 向右 -> 向右 -> 向下
     * 2. 向右 -> 向下 -> 向右
     * 3. 向下 -> 向右 -> 向右
     * 示例 2:
     * 
     * 输入: m = 7, n = 3
     * 输出: 28
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        if (!(1 <= m && 1 <= n)) {
            return 0;
        }
        int oneWayStep = Math.min((m - 1), (n - 1)); // Math.min(向下移动的步数 , 向右移动的步数)
        if (oneWayStep == 0) {
            return 1;
        }
        int step = (m - 1) + (n - 1); // 向下移动的步数 + 向右移动的步数
        // 按排序组合的方式计算:
        // step*(step-1)*(step-2)*...*(step-downStep+1)/(downStep*(downStep-1)*...*2*1)
        int i = 1;
        long result = 1;
        while (i <= oneWayStep) {
            result *= (step - i + 1);
            result /= i;
            i++;
        }
        return (int)result;
    }
    
    /**
     * 63. 不同路径 II
     * 
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     * 
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     * 
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     * 
     * 
     * 
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     * 
     * 说明：m 和 n 的值均不超过 100。
     * 
     * 示例 1:
     * 
     * 输入:
     * [
     *   [0,0,0],
     *   [0,1,0],
     *   [0,0,0]
     * ]
     * 输出: 2
     * 解释:
     * 3x3 网格的正中间有一个障碍物。
     * 从左上角到右下角一共有 2 条不同的路径：
     * 1. 向右 -> 向右 -> 向下 -> 向下
     * 2. 向下 -> 向下 -> 向右 -> 向右
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int rows = obstacleGrid.length;
        if (rows == 0) {
            return 0;
        }
        int cols = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows - 1][cols - 1] == 1) {
            return 0;
        }
        // 动态规划
        // 第一行非障碍物节点obstacleGrid[0][col] = obstacleGrid[0][col - 1]
        // 后续行非障碍物节点obstacleGrid[row][col] = obstacleGrid[row-1][col] + obstacleGrid[row][col-1]
        // 障碍物节点obstacleGrid[row][col] = 0
        obstacleGrid[0][0] = 1;
        for (int col = 1; col < cols; col++) {
            if (obstacleGrid[0][col] == 0) {
                obstacleGrid[0][col] = obstacleGrid[0][col - 1];
            } else {
                obstacleGrid[0][col] = 0;
            }
        }
        for (int row = 1; row < rows; row++) {
            if (obstacleGrid[row][0] == 0) {
                obstacleGrid[row][0] = obstacleGrid[row - 1][0];
            } else {
                obstacleGrid[row][0] = 0;
            }
            for (int col = 1; col < cols; col++) {
                if (obstacleGrid[row][col] == 0) {
                    obstacleGrid[row][col] += obstacleGrid[row][col - 1];
                    obstacleGrid[row][col] += obstacleGrid[row - 1][col];
                } else {
                    obstacleGrid[row][col] = 0;
                }
            }
        }
        return obstacleGrid[rows - 1][cols - 1];
    }
}
